#include <iostream>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <iterator>
using namespace std;
template <class T>
int partition(T* a, int left, int right){
    int i = left, j = right;
    while(i<j){
        while(i<j &&a[j]>=a[left]) j--;
        while(i<j &&a[i]<=a[left]) i++;
        if(i!=j)
            swap(a[i],a[j]);
    }
    swap(a[i],a[left]);
    return i;
}

template <class T>
void quicksort(T *a, int left, int right){
    if(left>=right) return;
    int index = partition(a, left, right);
    quicksort(a, left, index-1);
    quicksort(a, index+1, right);
    
}
template <class T>
void quicksort(T *a, int size){
    quicksort(a, 0, size-1);
    
}


typedef ostream_iterator<float> int_it ;
int main()
{
    
    srand(time(NULL));
    const int size  =100;
    float *a = new float[size];
    for(int i=0;i<size;i++){
        a[i] = (float)(rand()%10000)/100;
    }
    copy(a,a+size,int_it(cout, " "));
    cout<<endl;
    quicksort<float>(a, size);
    cout<<endl;
    copy(a,a+size,int_it(cout, " "));
	return 0;
}
